/*
Given a set of non overlapping intervals
Example 1 :(1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)

Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be 
(1,5) (6, 33) (35, 40)

This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

typedef pair<int, int> PII;


class point_t 
{
public:
    point_t(int n, bool start):num(n), startPoint(start){}
    bool startPoint;
    int num;
};

bool comp(point_t l, point_t r)
{
    return l.num < r.num;
}

PII findIntersection(vector<PII> &intervals)
{
    PII ans;
    vector<point_t> points;
    int k = 0;
    int maxK = 0;
    int index = 0;
    for (int i = 0; i < intervals.size(); i++) {
        points.push_back(point_t(intervals[i].first, true));
        points.push_back(point_t(intervals[i].second, false));
    }
    sort(points.begin(), points.end(), comp);
    for (int i = 0; i < points.size(); i++) {
        if (points[i].startPoint == true) k++;
        else k--;
        if (k >= maxK) {
            index = i;
            maxK = k;
	}
    }
    ans.first = points[index].num;
    ans.second = points[index+1].num;
    cout << ans.first << " " << ans.second << endl;
    return ans;
}

int main(int argc, char **argv)
{
    srand ( time(NULL) );
    vector<PII> intervals;
    vector<point_t> points;

    for (int i = 0; i < 7; i++) {
	int start = rand()%30;
	int end = rand()%30;
	if (end <= start) {i--; continue;}
	intervals.push_back(make_pair(start, end));
    }
    for (int i = 0; i < intervals.size(); i++) {
	cout << intervals[i].first << " " << intervals[i].second << endl;
    }
    cout << endl;
    /*intervals.push_back(make_pair(1, 5));
    intervals.push_back(make_pair(6,15));
    intervals.push_back(make_pair(7, 21));
    intervals.push_back(make_pair(8, 12));
    intervals.push_back(make_pair(15, 30)); */
    PII ans = findIntersection(intervals);
}
